\documentclass[a4paper]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}

%%\usepackage{algorithm}
%%\usepackage{algorithmic}

%%%%%%%%%% marges %%%%%%%%%%

%%\usepackage{layout}
\usepackage[top=3cm, bottom=3cm, left=4cm, right=4cm]{geometry}



\begin{document}

\title{Implémentation d'une bibliothèque de gestion de threads.}

\author{ David \bsc{Boust}, Aylli \bsc{Chuquillanqui}, Cyrille
  \bsc{Piacibello},\\ Nicolas \bsc{Retrain}, Nicolas \bsc{Verdier}}

\maketitle

\section*{Introduction}

Ce projet a pour objectif l'implémentation d'une bibliothèque de
gestion de threads, proche des fonctions connues \verb?pthreads?.
Nous utiliserons pour cela les fonctions de manipulations de contexte,
des variables et structures propres à notre implémentation.  Nous nous
sommes fixés également comme objectif de visualiser sur des tests
conséquents la différence de temps d'execution entre un programme
utilisant la bibliotheque \verb?pthread? et un programme utilisant
notre bibliotheque de thread.  Enfin, nous régler les problèmes posés
par le thread principal (main).  

Le rapport s'organise comme suit : En premier lieu, nous rappelons les
mécanismes mis en jeu dans la création d'une bibliotheque de thread,
cette partie est commune au rapport intermédiaire livré précedemment.
Ensuite nous expliquons les problèmes que nous avons rencontrés, puis
nous discutons des résultats obtenus.

\newpage
\section{Structures et types abstraits de données utilisés}

\indent Le première étape du projet a bien évidemment été de faire des choix d'
implémentation notamment vis-à-vis de la composition des champs de notre 
structure \verb?thread_s?.\\

\subsection{La structure thread\_s}

Cette dernière contient trois champs d'entiers, l'un pour l'identifiant du 
thread, l'autre pour son statut et le dernier pour la position du thread dans la pile. A cela s'ajoute un contexte propre à chaque 
thread, ainsi qu'un champ $void$ $*$, qui correspond à la valeur de retour de la
fonction s'exécutant sur le thread.\\

\begin{center}
  \begin{tabular}{| c | c |}
    \hline
    Nom du champs & Type du champs \\
    \hline
    Identifiant & Entier\\
    Statut & Booléen \\
    Contexte & Pointeur vers une structure u\_context \\
    Valeur de retour & Pointeur générique\\
    Valeur de pile (valgrind) & Entier\\
    \hline
  \end{tabular}
\end{center}

\subsection{Enregistrement des threads}

\indent Nous avons également été amenés à construire un type abstrait
de donnés, qui permettra d'enregistrer tous les threads en attente
d'exécution. A la base de ce TAD, nous avons la structure nommée
\verb?thread_list?. Celle-ci est une liste chainée:
composée d'un champ $thread$ $*$ ainsi que d'un pointeur amenant au
prochain thread de cette liste. Un champ $unsigned$ $int$ se rajoute
au tout. Il correspond au numéro du thread qui a été ajouté à la
liste.\\ \\ 
\indent Afin de pouvoir gérer simplement ces structures décrites
au-dessus, nous avons implémenté les fonctions suivantes. Ainsi concernant la
structure \verb?thread_list?, nous avons développé les fonctions
$init\_thread\_list$, $add\_thread$, $get\_thread$, $remove\_thread$
et $print\_thread\_list$.\\ La fonction $init\_thread\_list$, comme
son nom l'indique, initialise une \verb?thread_list? avec les champs
mis à \verb?NULL? et le numéro mis à zéro.\\
La fonction $add\_thread$, quant à elle prend en paramètre une liste de thread et
un thread que nous souhaitons ajouter à cette liste. Durant l'ajout, on veille 
bien à ajouter le thread à la fin de la liste, à ce que le suivant soit 
\verb?NULL?, et qu'enfin le numéro soit incrémenté de un.\\
La fonction $get\_thread$ prend une liste de thread et renvoie un de ses threads
choisi de façon aléatoire. Pour cela, nous déterminons le nombre de thread 
appartenant à la liste et nous choissisons un nombre compris entre le nombre de
thread et zéro. Puis nous prenons le premier thread ayant un numéro supérieur à
ce nombre. Dans le cas où la liste est vide, nous renvoyons le pointeur 
\verb?NULL?.\\
La fonction $remove\_thread$ enlève de la liste passée en paramètre, le thread 
qui est lui aussi passé en paramètre. Pour cela, nous parcourons la liste jusqu'à 
trouver 
le thread en question. Ensuite, nous libérons la mémoire allouée dans les 
différents champs du thread, ainsi que le thread lui-même dans le cas où le 
thread a bien été trouvé dans la liste.\\ 
La fonction $print\_thread\_list$ affiche les numéros des threads de la liste 
passée en paramètre. Il s'agit d'une fonction d'aide au débogage.\\
\newpage
\section{Gestion des threads}

\indent Une fois notre format de thread décidé, nous avons commencé à
implémenter les fonctions de gestion de ces threads, c'est-à-dire les
fonctions qui seront fournis au client qui souhaite utiliser notre
bibliothèque. Ainsi les fonctions $thread\_create$, $thread\_self$,
$thread\_yield$, $thread\_join$ et $thread\_exit$ ont été faites.\\ La
fonction $thread\_create$ va initialiser un thread passé en
paramètre. Elle doit prendre en compte le fait que le thread du main a
été ou non créé.  Dans le cas où c'est la première fois qu'on utilise
cette fonction, il faut veiller à ajouter le thread du $main$ dans la
liste des threads en cours. Dans tous les cas, nous ajoutons le thread
en paramètre dans la liste en ayant préalablement initialisé son
statut à un, son identifiant et son contexte.\\

La fonction $thread\_self$ se charge de récupérer le
thread courant.\\ 

La fonction $thread\_yield$ permet de passer la main
à un autre thread.  Pour cela, le thread courant doit être remplacé
par un nouveau thread pris dans la liste des threads. Si il n'y a
aucun thread dans cette dernière, la fonction renvoie une erreur et le
thread courant est maintenu. Sinon, nous faissons un $swapcontext$
entre les deux.\\

La fonction $thread\_join$ quant à elle permet au
thread courant d'attendre la fin d'exécution du thread passé en
paramètre. Pour ce faire, la fonction attend que le statut du thread
qu'elle attend, devienne égale à zéro, à l'aide d'une boucle $while$
qui fait des $thread\_yield$. Une fois cela fait, on met dans la
valeur de retour, le numéro du thread, dans le cas où elle n'est pas
nulle.\\

La fonction $thread\_exit$ termine le thread courant en
remplissant le champ $void$ $*$ avec la valeur passée en paramètre. Il
est à noter que le statut du thread courant est mis à zéro. De plus,
le thread courant est à enlever de la liste des threads en
cours. Enfin, nous donnons la main à un autre thread.  \\\\ \indent
Nous avons implémenté ces fonctions afin d'avoir un comportement
assez semblable avec la bibliothèque 
\verb?pthread.h?, et cela pour faire une comparaison.
\newpage
\section{Gestion des contextes}
\indent Concernant l'ensemble des fonctions gérant les $thread\_t$, nous avons 
été amené à gérer leurs contextes. Ainsi la bibliothèque \verb?ucontext.h? 
nous a été utile dans l'ensemble du projet, notamment les fonctions 
$makecontext$, $getcontext$ et $swapcontext$.\\
La fonction $getcontext$ remplit la structure $ucontext\_t$ $*$ passée en 
paramètre par le contexte actuel. Nous l'avons utilisée lors de la création des 
threads. Ainsi chaque thread avait un contexte, sauf le thread du $main$.\\
La fonction $makecontext$ modifie le contexte pointé en paramètre (obtenu grâce
à $getcontext$). Afin de bien utiliser cette fonction, il est nécessaire 
d'allouer la pile du contexte et de définir le successeur. Ensuite le contexte est
activé et la fonction passée en paramètre est appelée. Nous avons utilisé cette
fonction, une fois de plus lors de la création des threads.\\
La fonction $swapcontext$ sauvegarde le contexte actuel dans la structure 
$ucontext$ pointée et active le contexte pointé par cette dernière. Cette 
fonction a été utilisée lors de la création de thread, mais également lors du 
$thread\_yield$, c'est-à-dire, lorsque nous souhaitons passer la main à un autre
thread.

\section{Le cas du main}
%% Parler du cas du main
Très vite, nous nous sommes rendu compte que nous devions gérer au mieux le cas du \verb?main?. En effet, il devait être possible de donner la main au \verb?main? afin de permettre de continuer les différentes tâches. Nous avons donc placé le \verb?main? dans la liste des threads en cours d'éxécution. Comme il s'agit du premier thread, nous avons géré son cas de la façon suivante : il existe une variable globale qui sert de booléen afin de savoir si le \verb?main? a été initialisé ou non. Ainsi quand la variable nommée \verb?main_initialized? vaut zéro, lors de l'appel de la fonction \verb?thread_create?, un thread représentant le \verb?main?, est créé en plus du thread voulu et ajouté dans la liste des thread en cours. Puis la variable \verb?main_initialized? est mis à un.
  

\section{Le cas des fuites mémoires}
%% Fuite mémoire avec valgrind 

Nous avons voulu vérifier si notre bibliothèque de thread avait ou non des fuites mémoire. Pour ce faire, nous avons dû ajouter un champ à notre structure \verb?thread? que nous avons appellé \verb?valgrind?. Ce champ renseignait la position du thread dans la pile. Il devait donc être initialisé lors de la création du thread puis nous devions la retirer de la pile lors de la destruction du thread.\\
Grâce à cela, nous nous sommes rendu compte qu'il y avait des fuites mémoires dans notre implémentation. Nous avons essayé de régler celles-ci. Cependant, plus nous essayions de limiter les fuites mémoires, moins notre implémentation fonctionnait. Nous avions notamment des \verb?segfaults? qui apparaissaient aléatoirement lorsqu'on libérait les \textit{ucontext}.\\
Nous avons finalement pu régler tous les problèmes de fuite mémoire excepté la libération des ucontext (dans la fonction \textit{remove\_thread} du fichier list\_thread.c qui pose encore problème lors d'exécutions avec beaucoup de thread (exemple: fibonacci).


\newpage


\section{Tests des fonctions}
\indent Nous avons testé notre biliothèque grâce au fichier \verb?exemple.c? fourni au début du projet. Nous avons ainsi pu vérifier que notre bibliothèque était fonctionnelle et correspondait à nos attentes. 
Ainsi au début lors des tests avec le fichier \verb?exemple.c?, nous étions confrontés à des boucles infinies. 
Ceci était dû à une mauvaise implémentation des ucontexts. Ainsi lors de l'appel des fonctions $thread\_yield$, les threads ne donnaient pas la main 
aux autres. Ceci faisait que la fonction $thread\_join$ attendait indéfiniment
la fin de son thread passé en paramètre.\\
\indent Concernant les fonctions de gestion de la structure
\verb?thread_list?, nous avons verifié que les fonctions faisaient ce
que nous souhaitions. Pour cela, nous avons utilisé notre fonction
$print\_thread\_list$. Ainsi, nous avons dû modifier les fonctions
$get\_thread$ et $add\_thread$. En effet, il y avait des problèmes
d'indices que nous avons réglés. Ainsi la première version de
$add\_thread$ consistuait à mettre son idenfiant à celui du premier
plus un, ce qui faisait que tous les threads, hormis le premier, avaient
le même identifiant.

%% Parler des tests sur fibo => notre biblio moins rapide que pthread
%% Autres tests ?

\indent Par la suite, nous avons nous-même réaliser deux tests différents. Ainsi nous avons implémenté \verb?fibo_thread.c? et \verb?Somme_DC.c?. Pour le premier fichier, il s'agit de calculer la célèbre suite de Fibonacci à l'aide de thread. Le second consiste à générer un tableau de nombre aléatoire, de taille entrée en paramètre. Puis à l'aide des threads qui divisent le tableau en deux, récursivement, afin de calculer la somme des nombres compris dans le dit tableau.  


%% Avantage + inconvénients de notre lib ?
Nous avons pu voir que de façon générale, notre bibliothèque est plus lente que la bibliothèque \verb?pthread?. Nous pouvons notamment le constater lors des tests sur la suite de Fibonacci. Nous avons ainsi les graphiques suivant :\\ \\
\includegraphics[scale=0.5]{Fibo.png}
\\
\begin{figure}[!t]
\centering
\includegraphics[scale=0.5]{Graphe_Comparatif_Somme_Tableau.png}
\caption{Graphe comparatif pour la somme}
\end{figure}
\\
\\

Comme nous pouvons le constater, pour des calculs de Fibonacci
inférieurs ou égal à 15, notre bibliothèque rivalise voire est plus
performante que la bibliothèque \verb?pthread?.  en ce qui concerne le
test ``Somme des élèments d'un tableau``(divide and conquer) notre
bibliothèque est toujours plus lente que la bibliohtèque pthread, mais
reste cependant performante ! Remarquons que concernant le calcul de
la somme des éléments d'un tableau, nous ne maintenons en permanence
que log(n) threads, ou n est la taille du tableau, ce qui est bien
plus léger en terme de consomation que le calcul de la suite
Fibonacci.
\newpage
\section*{Conclusion}


Nous avons pu implémenter notre bibliothèque de thread basique, et
nous avons même pu aborder le cas du thread principal. Il est
cependant à regretter que nous n'ayions pas eu plus de temps pour
régler les fuites mémoires et peut-être aborder d'autres objectifs
plus avancés.
Ce projet nous a permis de mettre en application les connaissance sur
les systèmes d'exploitations de type UNIX.En effet, nous avons compris
les problématiques liées notamment aux fuites mémoires dans notre cas.
Nous savons donc maintenant ce qui se passe réellement lorsqu'on
utilise des threads dans un programme.

\end{document}
